﻿#region Libraries
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;
using System.Windows;
using System.ComponentModel;
using System.Diagnostics;
using System.Windows.Threading;
using System.Threading;
#endregion

namespace LabyWPF3D
{
	/// <summary>
	/// Compass directions
	/// </summary>
	public enum Compass
	{
		None = 0, 
		North = 1,
		South = 2, 
		East = 4, 
		West = 8,
		All = South | North | West | East
	}

	public enum Notification
	{
		BeforeMove = 0,
		AfterSuccessfullMove = 1,
		AfterFailedMove = 2
	}

	/// <summary>
	/// Possition
	/// </summary>
	public struct position {
		public int row;
		public int col;
		public Compass left;
		public Compass right;
		public Compass front;
		public Compass back;
	}

	/// <summary>
	/// Worker notification
	/// </summary>
	struct notification
	{
		public Compass direction;
		public position currentPosition;
		public Notification type;
	}

	/// <summary>
	/// Labyrinth solving class
	/// </summary>
	public class Labyrinth
	{
		#region Constants
		/// <summary>
		/// Debug mode
		/// </summary>
		public const bool DEBUG = false;
		/// <summary>
		/// Max number of rows for the labyrinth
		/// </summary>
		public const int MAX_ROWS = 1000;
		/// <summary>
		/// Max number of columns for the labyrinth
		/// </summary>
		public const int MAX_COLS = 1000;
		/// <summary>
		/// Wall of the labyrinth
		/// </summary>
		public const int WALL = 0;
		/// <summary>
		/// Path where the figure can go
		/// </summary>
		public const int PATH = 1;
		/// <summary>
		/// Start position
		/// </summary>
		public const int START = 2;
		/// <summary>
		/// Finish position
		/// </summary>
		public const int FINISH = 4;
		/// <summary>
		/// Was Here path
		/// </summary>
        public const int WasHere = 8;
        /// <summary>
        /// DeadEnd path 
        /// *second time, when turn on the WasHere path, that path becomes - DeadEnd
        /// </summary>
        public const int DeadEnd = 7;            
		/// <summary>
		/// Any value where it's possible to go
		/// </summary>
		public const int POSSIBLE = PATH | START | FINISH | WasHere;
		#endregion

		#region Properties
		/// <summary>
		/// Labyrinth matrix
		/// </summary>
		private int[,] matrix;
		/// <summary>
		/// Loaded solution matrix
		/// </summary>
		private int[,] solution;
		/// <summary>
		/// Generated solution matrxix
		/// </summary>
		private int[,] generatedSolution;
		/// <summary>
		/// Labyrinth height (number of rows):
		/// </summary>
		private int rows = 0;
		/// <summary>
		/// Labyrinth width (number of cols):
		/// </summary>
		private int cols = 0;
		/// <summary>
		/// Name of the file containing matrix:
		/// </summary>
		private String filename;
		/// <summary>
		/// Ball position
		/// </summary>
		public position currentPosition;
		/// <summary>
		/// Previous ball position
		/// </summary>
        public position previousPosition;
		/// <summary>
		/// Finish position
		/// </summary>
        public position finishPosition;
		/// <summary>
		/// Start position
		/// </summary>
        public position startPosition;
		/// <summary>
		/// Is generated matrix filtered
		/// </summary>
		private bool isFormated;
		/// <summary>
		/// Have we moved
		/// </summary>
		public bool moved = false;
		/// <summary>
		/// Background worker
		/// </summary>
		private BackgroundWorker worker;
		/// <summary>
		/// Execution timer
		/// </summary>
		public Stopwatch timer;
		/// <summary>
		/// Allow to use solution
		/// </summary>
		public bool useSolution = true;
        /// <summary>
        /// Latency
        /// </summary>
        public int latency = 150;
		#endregion

		/// <summary>
		/// Class constructor
		/// </summary>
		public Labyrinth() {
		}

		/// <summary>
		/// Reads the labyrinth matrix from file
		/// </summary>
		/// <param name="file">File name to read labyrinth from</param>
		public void ReadFromFile(String file) {
			string line;	// Temporary line
			string[] tmp;	// Temporary char array

			filename = file;
			matrix = new int[MAX_ROWS, MAX_COLS];
			currentPosition.left = Compass.East;
			currentPosition.right = Compass.West;
			currentPosition.front = Compass.South;
			currentPosition.back = Compass.North;
			cols = 0;
			rows = 0;

			try
			{
				StreamReader stream = new StreamReader(file);
				// Loop through the file line-by-line:
				while ((line = stream.ReadLine()) != null)
				{
					// New line - reset column counter:
					cols = 0;
					// Loop through the line:
					tmp = line.Split(new Char[] { ' ' });
					foreach (string s in tmp)
					{
						matrix[rows, cols] = int.Parse(s);
						// Current ball position:
						if (matrix[rows, cols] == START)
						{
							currentPosition.row = rows;
							currentPosition.col = cols;
							previousPosition = currentPosition;
							startPosition = currentPosition;
						}
						// Finish position:
						if (matrix[rows, cols] == FINISH)
						{
							finishPosition.row = rows;
							finishPosition.col = cols;
						}
						cols++;
					}
					rows++;
				}
				generatedSolution = matrix;
			}
			// Data file doesn't exist:
			catch (FileNotFoundException e)
			{
				Console.WriteLine("Error: " + e.Message);
			}
		}

		/// <summary>
		/// Loads solution matrix from file
		/// </summary>
		/// <param name="file">File name to read solution from</param>
		public void ReadSolutionFromFile(String file)
		{
			string line;		// Temporary line
			string[] tmp;		// Temporary char array
			int i = 0, j = 0;	// Rows/Columns

			solution = new int[MAX_ROWS, MAX_COLS];
			try
			{
				StreamReader stream = new StreamReader(file);
				// Loop through the file line-by-line:
				while ((line = stream.ReadLine()) != null)
				{
					// New line - reset column counter:
					j = 0;
					// Loop through the line:
					tmp = line.Split(new Char[] { ' ' });
					foreach (string s in tmp)
					{
						solution[i, j++] = int.Parse(s);
					}
					i++;
				}
			}
			// Data file doesn't exist:
			catch (FileNotFoundException e)
			{
				Console.WriteLine("Error: " + e.Message);
			}
		}
		
		/// <summary>
		/// Determinates if it's possible to move to specified direction
		/// </summary>
		/// <param name="direction">Direction</param>
		/// <returns>True if it's possible; False otherwise</returns>
		public bool CanGo(Compass direction)
		{
			switch (direction)
			{
				case Compass.North:
					return (currentPosition.row != 0 && (matrix[currentPosition.row - 1, currentPosition.col] & POSSIBLE) != 0);
				case Compass.East:
					return (currentPosition.col != cols - 1 && (matrix[currentPosition.row, currentPosition.col + 1] & POSSIBLE) != 0);
				case Compass.South:
					return (currentPosition.row != rows - 1 && (matrix[currentPosition.row + 1, currentPosition.col] & POSSIBLE) != 0);
				case Compass.West:
					return (currentPosition.col != 0 && (matrix[currentPosition.row, currentPosition.col - 1] & POSSIBLE) != 0);
				default:
					return false;
			}
		}

		/// <summary>
		/// Generates the report
		/// </summary>
		/// <param name="direction">Direction to go</param>
		/// <param name="pos">Current possition</param>
		/// <param name="type">Type of report</param>
		/// <returns>Generated report</returns>
		private notification SetReport(Compass direction, position pos, Notification type)
		{
			notification report;
			report.direction = direction;
			report.currentPosition = pos;
			report.type = type;
			return report;
		}

		/// <summary>
		/// Goes to the specified direction
		/// </summary>
		/// <param name="direction">Direction</param>
		/// <returns>True if move was possible; False otherwise</returns>
		public bool Go(Compass direction)
		{
			if (DEBUG)
			{
				Console.WriteLine();
				Console.WriteLine("My current coordinates are " + currentPosition.row + "x" + currentPosition.col);
				Console.WriteLine("Trying to move to " + direction);
			}
			// Go that way if we can:
			if (CanGo(direction)) {
                switch (generatedSolution[currentPosition.row, currentPosition.col])
                {
                    case PATH: //if current element is PATH, it become WasHere
                        generatedSolution[currentPosition.row, currentPosition.col] = WasHere;
                        break;
                    case WasHere: //if current element is WasHere, it become DeadEnd
                        if (IsCrossroad() && !CanGo(currentPosition.front))  //There are no finish, so it's - deadend
                        generatedSolution[currentPosition.row, currentPosition.col] = DeadEnd;
                        break;
                    case DeadEnd:
                        generatedSolution[currentPosition.row, currentPosition.col] = DeadEnd;
                        break;
                }
				switch (direction)
				{
					case Compass.North:
						currentPosition.row -= 1;
						break;
					case Compass.East:
						currentPosition.col += 1;
						break;
					case Compass.South:
						currentPosition.row += 1;
						break;
					case Compass.West:
						currentPosition.col -= 1;
						break;
				}
		
				// Turn left:
				TurnLeft();
				if (DEBUG)
				{
					Console.WriteLine("I've moved to " + direction);
					Console.WriteLine("My new coordinates are " + currentPosition.row + "x" + currentPosition.col);
					Console.WriteLine("My left is on " + currentPosition.left + " now");
					Console.WriteLine("My front is on " + currentPosition.front + " now");
				}
				return true;
			} else {
				// Turn left:
				TurnRight();
				if (DEBUG)
				{
					Console.WriteLine("I can't move to " + direction);
					Console.WriteLine("My coordinates remain as " + currentPosition.row + "x" + currentPosition.col);
					Console.WriteLine("My front is on " + currentPosition.front + " now");
					Console.WriteLine("My left is on " + currentPosition.left + " now");
				}
				return false;
			}
		}

		/// <summary>
		/// Turns left
		/// </summary>
		public void TurnLeft()
		{
			switch (currentPosition.left)
			{
				case Compass.North:
					currentPosition.left = Compass.West;
					currentPosition.right = Compass.East;
					currentPosition.front = Compass.North;
					currentPosition.back = Compass.South;
					break;
				case Compass.East:
					currentPosition.left = Compass.North;
					currentPosition.right = Compass.South;
					currentPosition.front = Compass.East;
					currentPosition.back = Compass.West;
					break;
				case Compass.South:
					currentPosition.left = Compass.East;
					currentPosition.right = Compass.West;
					currentPosition.front = Compass.South;
					currentPosition.back = Compass.North;
					break;
				case Compass.West:
					currentPosition.left = Compass.South;
					currentPosition.right = Compass.North;
					currentPosition.front = Compass.West;
					currentPosition.back = Compass.East;
					break;
			}
		}

		/// <summary>
		/// Turns right
		/// </summary>
		public void TurnRight()
		{
			switch (currentPosition.left)
			{
				case Compass.North:
					currentPosition.left = Compass.East;
					currentPosition.right = Compass.West;
					currentPosition.front = Compass.South;
					currentPosition.back = Compass.North;
					break;
				case Compass.East:
					currentPosition.left = Compass.South;
					currentPosition.right = Compass.North;
					currentPosition.front = Compass.West;
					currentPosition.back = Compass.East;
					break;
				case Compass.South:
					currentPosition.left = Compass.West;
					currentPosition.right = Compass.East;
					currentPosition.front = Compass.North;
					currentPosition.back = Compass.South;
					break;
				case Compass.West:
					currentPosition.left = Compass.North;
					currentPosition.right = Compass.South;
					currentPosition.front = Compass.East;
					currentPosition.back = Compass.West;
					break;
			}
		}

		/// <summary>
		/// Counts number of possible ways to go (backwards not included)
		/// </summary>
		/// <returns>Number of ways</returns>
		public int CountDirections()
		{
			return Convert.ToInt32(CanGo(currentPosition.left)) + Convert.ToInt32(CanGo(currentPosition.right));
		}

		/// <summary>
		/// Determinates if there's a crossroad at current possition
		/// </summary>
		/// <returns>True, if we have a crossroad, False - otherwise</returns>
		public bool IsCrossroad()
		{
			return CountDirections() > 0;
		}

		/// <summary>
		/// Is specified point a deadend
		/// </summary>
		/// <param name="pos">Position</param>
		/// <returns>True if it's deadend, false otherwise</returns>
		public bool IsDeadend(position pos)
		{
			int directions = 0;
			if (pos.col == 0 || pos.row == 0 || pos.row == rows - 1 || pos.col == cols - 1)
				return false;
			directions = Convert.ToInt32((matrix[pos.row - 1, pos.col] & POSSIBLE) != 0) +
				Convert.ToInt32((matrix[pos.row, pos.col + 1] & POSSIBLE) != 0) +
				Convert.ToInt32((matrix[pos.row + 1, pos.col] & POSSIBLE) != 0) +
				Convert.ToInt32((matrix[pos.row, pos.col - 1] & POSSIBLE) != 0);
			return directions < 2;
		}

		/// <summary>
		/// Checks if labyrinth is solved
		/// </summary>
		/// <returns>True, if labyrinth is solved, False - otherwise</returns>
		public bool IsSolved()
		{
			return (currentPosition.col == finishPosition.col && currentPosition.row == finishPosition.row);
		}

		/// <summary>
		/// Checks if we have the correct path already
		/// </summary>
		/// <returns>True, if we have, False otherwise</returns>
		public bool KnownSolution()
		{
			return (solution != null && useSolution);
		}

		/// <summary>
		/// Saves solution matrix to file
		/// </summary>
		/// <param name="file">File to save to</param>
		/// <returns>True, if we saved, False otherwise</returns>
		public bool SaveSolutionToFile(String file)
		{
			FormatGeneratedMatrix();
			try
			{
				StreamWriter stream = new StreamWriter(new FileStream(file, FileMode.Create, FileAccess.Write, FileShare.None));
				// Loop through rows:
				for (int i = 0; i < rows; i++)
				{
					// Loop through columns:
					for (int j = 0; j < cols; j++)
					{
						// Write:
						stream.Write(generatedSolution[i, j]);
						if (j != cols - 1)
							stream.Write(" ");
					}
					if (i != rows - 1)
						stream.Write("\r\n");
				}
				stream.Close();
				return true;
			}
			catch (IOException e)
			{
				Console.WriteLine("Error: " + e.Message);
				return false;
			}
		}

		/// <summary>
		/// Marges solution to the main labyrinth:
		/// </summary>
		public void MargeSolution()
		{
			// Must have the solution:
			if (KnownSolution()) {
				// Loop through rows:
				for (int i = 0; i < rows; i++)
				{
					// Loop through columns:
					for (int j = 0; j < cols; j++)
					{
						// Replace all cells except for finish and start:
						if (matrix[i, j] != START && matrix[i, j] != FINISH)
						{
							matrix[i, j] = solution[i, j];
						}
					}
				}
			}
		}

		/// <summary>
		/// Formats generated solution matrix
		/// </summary>
		protected void FormatGeneratedMatrix()
		{
			// Format only once:
			if (!isFormated)
			{
				// Position
				position pos = new position();

				// Replace unvisited paths:
				for (int i = 0; i < rows; i++)
				{
					for (int j = 0; j < cols; j++)
					{
						pos.row = i;
						pos.col = j;
                        if ((generatedSolution[i, j] != START) && (generatedSolution[i, j] != FINISH) && (generatedSolution[i, j] == PATH || IsDeadend(pos)))
							generatedSolution[i, j] = WALL;
					}
				}
				// Replace visited paths:
				for (int i = rows; i >= 0; i--)
				{
					for (int j = cols; j >= 0; j--)
					{
                        if (generatedSolution[i, j] == WasHere)	
                        generatedSolution[i, j] = PATH;
						if (i == finishPosition.row && j == finishPosition.col)
							generatedSolution[i, j] = FINISH;
                        if (generatedSolution[i, j] == DeadEnd)
                            generatedSolution[i, j] = WALL;
					}
				}
				// Remove deadends:
				for (int i = 0; i < rows; i++)
				{
					for (int j = cols; j >= 0; j--)
					{
						pos.row = i;
						pos.col = j;
                        if ((IsDeadend(pos) || generatedSolution[i, j] == DeadEnd) && generatedSolution[i, j]!=FINISH)
							generatedSolution[i, j] = WALL;
                        
					}
				}
				// Remove deadends (for the last time):
				for (int i = rows; i >= 0; i--)
				{
					for (int j = 0; j < 0; j++)
					{
						pos.row = i;
						pos.col = j;
                        if ((IsDeadend(pos) || generatedSolution[i, j] == DeadEnd)  && generatedSolution[i, j] != FINISH)
							generatedSolution[i, j] = WALL;
					}
				}
				isFormated = true;
			}
		}

		/// <summary>
		/// Clears previous data
		/// </summary>
		public void Clear()
		{
			if (filename != null)
				ReadFromFile(filename);
			generatedSolution = new int[MAX_ROWS, MAX_COLS];
			isFormated = false;
		}

		#region Debugging methods
		/// <summary>
		/// Dumps the matrix and her dimentions (for debugging purposes)
		/// </summary>
		public void Dump(int[,] m)
		{
			Console.WriteLine();
			Console.WriteLine("Data filename: " + filename);
			Console.WriteLine("Number of rows: " + rows);
			Console.WriteLine("Number of columns: " + cols);
			Console.WriteLine("The matrix:");
			// Dump the matrix:
			for (int i = 0; i < rows; i++)
			{
				for (int j = 0; j < cols; j++)
				{
					System.Console.Write(m[i, j] + " ");
				}
				Console.WriteLine();
			}
			Console.WriteLine();
		}
		#endregion

		#region Interface methods
		/// <summary>
		/// Gets number of rows
		/// </summary>
		/// <returns>Number of rows</returns>
		public int GetRows()
		{
			return rows;
		}

		/// <summary>
		/// Gets number of columns
		/// </summary>
		/// <returns>Number of columns</returns>
		public int GetCols()
		{
			return cols;
		}

		/// <summary>
		/// Get the labyrinth matrix
		/// </summary>
		/// <returns>The Matrix</returns>
		public int[,] GetMatrix()
		{
			return matrix;
		}

		/// <summary>
		/// Get the solution of the labyrinth
		/// </summary>
		/// <returns>The Matrix</returns>
		public int[,] GetSolution()
		{
			return solution;
		}

		/// <summary>
		/// Get current position
		/// </summary>
		/// <returns>Current position</returns>
		public position GetCurrentPosition()
		{
			return currentPosition;
		}

		/// <summary>
		/// Returns cell value from the matrix
		/// </summary>
		/// <param name="row">Row number</param>
		/// <param name="col">Column number</param>
		/// <returns>Cell value</returns>
		public int GetCell(int row, int col) {
			if (row <= rows && col <= cols)
				return matrix[row, col];
			return 0;
		}

		/// <summary>
		/// Gets generated solution
		/// </summary>
		/// <returns>The Matrix</returns>
		public int[,] GetGenetatedSolution()
		{
			FormatGeneratedMatrix();
			return generatedSolution;
		}
		#endregion

		#region Solving
		/// <summary>
		/// Solves the labyrinth
		/// </summary>
		public void Solve(object sender, DoWorkEventArgs e)
		{
			timer = new Stopwatch();
			timer.Start();

			// Init background worker:
			worker = (BackgroundWorker)sender;

			// If we have solution, marge it to the main labyrinth:
			MargeSolution();
			// Loop till we find the solution of the labyrinth:
			while (!IsSolved())
			{
				// Navigate and report progress:
				worker.ReportProgress(1, SetReport(currentPosition.left, currentPosition, Notification.BeforeMove));
				moved = Go(currentPosition.left);
				if (moved)
				{
					worker.ReportProgress(1, SetReport(currentPosition.left, currentPosition, Notification.AfterSuccessfullMove));
				}
				else
				{
					worker.ReportProgress(1, SetReport(currentPosition.left, currentPosition, Notification.AfterFailedMove));
				}
				// Was canceled:
				if (worker.CancellationPending)
				{
					e.Cancel = true;
					break;
				}
				Thread.Sleep(this.latency);
			}
			solution = generatedSolution;
			//Dump(GetGenetatedSolution());
			timer.Stop();
		}
		#endregion
	}
}